package org.aplombh.java.awcing.basic.math.euler;

import java.util.Scanner;

/**
 * 给定 n 个正整数 ai，请你求出每个数的欧拉函数。
 * <p>
 * 欧拉函数的定义
 * 1∼N 中与 N 互质的数的个数被称为欧拉函数，记为 ϕ(N)。
 * 若在算数基本定理中，N=pa11pa22…pamm，则：
 * ϕ(N) = N×p1−1p1×p2−1p2×…×pm−1pm
 * 输入格式
 * 第一行包含整数 n。
 * <p>
 * 接下来 n 行，每行包含一个正整数 ai。
 * <p>
 * 输出格式
 * 输出共 n 行，每行输出一个正整数 ai 的欧拉函数。
 * <p>
 * 数据范围
 * 1≤n≤100,
 * 1≤ai≤2×109
 * 输入样例：
 * 3
 * 3
 * 6
 * 8
 * 输出样例：
 * 2
 * 2
 * 4
 */
public class EulerFunction_873 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        EulerFunction eulerFunction = new EulerFunction();
        for (int i = 0; i < n; i++) {
            int x = scanner.nextInt();
            System.out.println(eulerFunction.euler(x));
        }
    }
}

class EulerFunction {
    int euler(int x) {
        int res = x;
        for (int i = 2; i <= x / i; i++) {
            if (x % i == 0) {
                // E(x) = x * ( 1 - 1/p1) * ( 1 - 1/p2) * ... * ( 1 - 1/pk)
                res = res / i * (i - 1);
                while (x % i == 0) {
                    x /= i;
                }
            }
        }
        if (x > 1) res = res / x * (x - 1);
        return res;
    }
}
